package hot;

import java.util.ArrayList;
import java.util.List;

public class siliu {
//    https://leetcode.cn/problems/permutations/submissions/674543361/  46 力扣hot 回溯全排列问题

        public static List<List<Integer>> ret=new ArrayList<>();
        public static List<Integer> path=new ArrayList<>();
        public static boolean[] check;
        public static List<List<Integer>> permute(int[] nums) {
            check=new boolean[nums.length];
            dfs(nums);
            return ret;
        }
        public static void dfs(int[] nums){
            //递归出口
            if(nums.length==path.size()){
                ret.add(new ArrayList(path));
                //原本这里回溯是要恢复现场的,但不在这里进行回溯恢复现场的操作
                //回溯操作：1.去掉path最后一个元素  2.修改check数组
                return;
            }
            //关注某个子问题在干什么 书写函数体
            for(int i=0;i<nums.length;i++){
                if(check[i]==false){
                    path.add(nums[i]);
                    check[i]=true;
                    dfs(nums);
                    //在这里进行恢复现场的操作
                    check[i]=false;
                    path.remove(path.size()-1);
                }

            }
        }

    public static void main(String[] args) {
        int[] nums={1,2,3};
        List<List<Integer>> permute = permute(nums);
        System.out.println(permute);

    }

}
